package a_doubleWrite;

import java.util.List;

/**
 * 120. 三角形最小路径和
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-07-25 19:21
 */
public class L120 {
    //直接递归超时
//    public int minimumTotal(List<List<Integer>> triangle) {
//        return dfs(triangle, 0, 0);
//    }
//
//    private int dfs(List<List<Integer>> triangle, int i, int j) {
//        if (i == triangle.size()) return 0;
//        return Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
//    }
    //使用记忆化递归
//    Integer[][] memo;
//
//    public int minimumTotal(List<List<Integer>> triangle) {
//        memo = new Integer[triangle.size()][triangle.get(triangle.size()-1).size()];
//        return dfs(triangle, 0, 0);
//    }
//
//    private int dfs(List<List<Integer>> triangle, int i, int j) {
//        if (i == triangle.size()) return 0;
//        //判断如果memo[i][j]已经有值，直接返回
//        if (memo[i][j] != null) return memo[i][j];
//        //否则递归赋值
//        memo[i][j] = Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
//        return memo[i][j];
//    }
    //自底向上动态规划
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] dp = new int[triangle.size()][triangle.get(triangle.size() - 1).size()];

        for (int i = triangle.size() - 1; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                if (i == triangle.size() - 1) {
                    dp[i][j] = triangle.get(i).get(j);
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
                }
            }

        }
        return dp[0][0];
    }
}
